#include <iostream>
#include <bitset>
#include <type_traits>

using ull = unsigned long long;
using std::cout,std::iostream,std::bitset;

template<class T>
class ReadNumber{
    char c;
    T w,n;
public:
    ReadNumber& operator>>(T &num)noexcept{
        c=(char)0,w=1,n=0;
        while(!isdigit(c)){
            if constexpr(!std::is_same_v<ull, T>){
                if(c=='-')w=-1;
            }
            c = getchar();
        }
        while(isdigit(c)){
            n = n*10 + (c-'0');
            c = getchar();
        }
        num = w*n;
        return *this;
    }
};

ull n, m, c, k, num, input, p, ans {1}, _;
bitset<64+5> bt;

ReadNumber<ull> readull;
#define cin readull

template<class T>
constexpr T safe_left_shift(const T t,const size_t n)noexcept{
    constexpr auto sizeof_t = sizeof(t)*8;
    return (n>=sizeof_t?0:t<<n);
}

int main(){
    cin>>n>>m>>c>>k;

    if(n==0 && m==0 && k==64){ //特判
        cout<<"18446744073709551616\n";
        return 0;
    }

    for(ull i=0;i<n;i++){
        cin>>input;
        num |= input; //所有编号占用的'1'的位置，把他并在一起
    }
    for(ull i=0;i<m;i++){
        cin>>p>>_;
        if(!((num>>p)&1) && !bt[p]){ //已有的n个编号里面没有出现过的规则，并且还未标记,bt用来去重
            k--;
            bt[p]=true;
        }
    }
    
    // for(int i=0;i<k;i++)ans*=2; //此时ans=所有(未排除n个已用规则),可以用的二进制位的组合
    ans = safe_left_shift(1ull, k); // 避开未定义行为
    cout<<ans-n<<'\n';//注意这里要去重，基本排列组合原理
}